class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int index = searchStep(nums, 0, nums.size()-1, target);

        if(index == -1) {
            return {-1, -1};
        }
        
        int indexL = index;
        while(--indexL >= 0 && nums[indexL] == nums[index]){
        }

        int indexR = index;
        while(++indexR < nums.size() && nums[indexR] == nums[index]){
        }

        return {++indexL, --indexR};
    }

    int searchStep(vector<int>& nums, int left, int right, int target) {
        while(left <= right){
            int mid = (left + right) >> 1;

            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }        
        }

        return -1;
    }
};